package daytwo;
/*链表  ( 单链表      双向链表 )
 * 1.链表 的翻转
 * 2.在链表中删除 指定值 可能不只删除一个  节点 
 * 很多事情 得  考虑 周到  三种情况 ①  在开头时 ②  在中间时 ③  在末尾时
 * 大多数题目得 思路考虑情况 都要 从 这三种情况 考虑得  只有  这样考虑  才能  可能 完整得写对
 * 对于删除得 情况 你考虑少得原因  很可能时  你见得  太少 
 * 
 * 
 * 
 * 链表常见的 面试题   :  ①:  笔试时 : 时间复杂度 一定要放在 第一位  只要  ac  就行
 * ②:  面试 时 :  还是 时间复杂度  首要  但是 尽量 的省空间 
 * 题目 一 :
 * 1.快慢指针 问题:
 * ① : 输入链表 头节点 ,链表长度 奇数 返回 中点 , 偶数 返回 上中点 (偶数  有两个中位数 )
 * ②:   ...........................偶数 返回 下中点
 * ③:................奇数 返回 中点 的前一个 节点, 偶数返回上中点的前一个节点
 * ④:...................................,偶数 返回下中点的 前一个节点 (这不就是 上中点嘛)
 * 上述的 题 就是coding   问题
 * 2. 直接放在 容器中  直接 算出 下标 比如 直接 放在 ArrayList 里面 算出 下标  直接 取出即可
 * 
 * 
 * 
 * 题目二:
 * 判断一个 链表是不是     回文链表      (跟字符串 中的判断 是不是 回文字符串 可以  雷同一下 )
 * 回文字符串 的 方法 很多 ;
 * 回文链表  的 话 笔试  直接  使用 一个栈 来解决  (明白吧   用** 栈  **  )
 * 优化 :  使用后             快慢指针   只需要 把 中点 指针 后面的 节点 加入栈 中 即可  这样可以 省一半 空间  时间复杂度 没有变 
 * 只是  常数 时间发生了变化
 * )
 * 还有其他的 方法 :  满指针 走到 中间节点 位置的 时候  将 中间指针后面的 一半节点  反转   然后比较 这个 流程 明白吧 
 * 最后 别忘了 把 逆序后 的后半 节点 给回复原来的 模样  有点 额外空间 复杂度为 O(1) 缺点 : coding  还是挺麻烦的 
 * 最后 这种方法  还是 值得  实践一下的  因为  这个涉及的 知识点  挺多的 
 * 
 * 
 * 
 * 题目三 :
 * 将 单向链表 按给定值  化成  小于的  在左边 等于的在中间 大于的在右边
 * 笔试:(只要 AC 就是 爷)  把 链表放在数组中
 * 面试:  使用 正式的方法 来写  就是涉及 一些算法逻辑的 方法来叙述 	  
 * 只用    六个       变量 直接 解决 这个问题  还能保持 稳定性 
 * 这个题 最关键的 地方在于  对于 引用数据类型的 变量 地址 引用指来指去 的  能够让你明白 很多 超出 该题之外的 知识
 * 链表  最烦的 地方就是  引用地址的 指 来 指去的   后面的二叉树 也是 这样
 * 链表  的题型  一定要注意 coding 不要感觉会了 就不练了 你上 你真 不行 
 * 
 * 
 * 
 * 题目四 :
 * 一种特殊的  单链表题目 除了  正常的  链表的Node 组成 之外  还有一个  random  指针 的 这个问题
 * 
 *  
 *  
 *  
 *  
 *  
 *  
 *  
 *题目 五:
 *给定两个 可能 有环 也可能没  环的 链表   	 实现 一个函数 如果 两个 链表 相交  请把 相交的 节点返回  不相交  返回 null
 *
 *
 *
 *题目 六:
 *不给 头节点  只给 你要删除的  节点    完成 给定节点的删除
 *做法:  将删除节点的下一个节点的 value  赋值 给 删除的节点 然后 删除 对应的下一个 节点   这是 找个 替死鬼
 *但是 无法删除 最后一个节点  
 *tailNode =null  这是 显然 的堆Java 的内存结构模型 不理解的行为
 *结论 : 做不到 不给 头节点  删除 指定节点 
 *p39(6)  这个视频 最后一点 让你 理解 Java 中内存的指向 原理 
 *内存 模型的理解 
 */
public class LinkedL {
	public static class Node{
		int value;
		Node next;
		public Node() {
			
		}
		public Node(int value) {
			this.value=value;
		}
	}
	
}
